#include <bits/stdc++.h>
using namespace std;

/*
2106. 摘水果
已解答
困难
相关标签
premium lock icon
相关企业
提示
在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。

另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的 最大总数 。

 

示例 1：


输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果
示例 2：


输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出：14
解释：
可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果
示例 3：


输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出：0
解释：
最多可以移动 k = 2 步，无法到达任一有水果的地方
 

提示：

1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）
1 <= amounti <= 104
0 <= k <= 2 * 105
*/

// 法一
class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int n = fruits.size();
        // 第一个位置 >= startPos - k 的下标
        auto it = lower_bound(fruits.begin(), fruits.end(), vector<int>{startPos - k, 0}, [](const vector<int>&a, const vector<int>&b) {
            return a[0] < b[0];
        });

        // 双指针来操作
        int left = it - fruits.begin();
        int right = left;
        int cnt = 0;

        // 覆盖startPos 左侧的水果
        while (right < n && fruits[right][0] <= startPos) {
            cnt += fruits[right][1];
            right++;
        }

        int ans = cnt;

        // 右边扩展窗口
        while (right < n && fruits[right][0] <= startPos + k) {
            cnt += fruits[right][1];
            // 路径检查 不满足就右移 再次检查
            while (right < n && left < n && fruits[right][0] * 2 - fruits[left][0] - startPos > k && fruits[right][0] + startPos - 2 * fruits[left][0] > k) {
                cnt -= fruits[left][1];
                left++;
            }
            ans = max(ans, cnt);
            right++;
        }

        return ans;
    }
};

// 法二
class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int n = fruits.size(), ans = 0;
        // 定义计算覆盖区间 [l, r] 所需的最小步数的函数
        auto step = [&](int l, int r) {
            // 如果整个区间在起点左侧：只需从起点走到左端点l
            if (r <= startPos) return startPos - l;
            // 如果整个区间在起点右侧：只需从起点走到右端点r
            else if (l >= startPos) return r - startPos;
            // 区间跨越起点：先到较近端点（左或右），再到较远端
            else return min(startPos - l, r - startPos) + r - l;
        };
        
        // 滑动窗口：l为左指针，r为右指针，sum为当前窗口水果总数
        for (int r = 0, l = 0, sum = 0; r < n; r++) {
            // 将右指针位置的水果加入窗口
            sum += fruits[r][1];
            // 当窗口不满足步数约束时，收缩左边界
            while (l <= r && step(fruits[l][0], fruits[r][0]) > k) {
                sum -= fruits[l][1]; // 移除左边界的水果
                l++;                // 左指针右移
            }
            // 更新最大水果数量
            ans = max(ans, sum);
        }
        return ans;
    }
};